import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 239. Sliding Window Maximum 滑动窗口最大值
 * https://leetcode.com/problems/sliding-window-maximum/description/
 */
class SlidingWindowMaximum {
    /**
     * 方法：使用双端队列维护当前窗口中的最大值索引
     * Args:
     *   nums: 整数数组
     *   k: 滑动窗口大小
     * Returns:
     *   每个滑动窗口的最大值组成的数组
     * Time: O(n) 每个元素最多入队和出队一次
     * Space: O(k) 双端队列最多存储k个元素
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!q.isEmpty() && nums[q.getLast()] <= nums[i]){
                q.removeLast();
            }
            q.addLast(i);
            if(i - q.getFirst() >= k){
                q.removeFirst();
            }
            if(i >= k-1){
                ans[i - k +1] = nums[q.getFirst()];
            }
        }
        return ans;
    }
}